/*
 * @Author: 缄默
 * @Date: 2021-12-13 21:21:03
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-13 22:10:12
 */

//龙与地下城游戏问题

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int minHP1(vector<vector<int>>& arr);

int main() {
    vector<vector<int>> arr {{-2, -3, 3}, {-5, -10, 1}, {-20, 30, -5}};
    cout << minHP1(arr) << endl;
}

int minHP1(vector<vector<int>>& arr) {
    if (arr.size() == 0) return 1;
    int row = arr.size();
    int col = arr[0].size();
    vector<vector<int>> dp(row--, vector<int>(col--));
    dp[row][col] = 0 < arr[row][col] ? 1 : 1 - arr[row][col];
    for (int i = row - 1 ; i >= 0 ; i--) {
        dp[i][col] = dp[i + 1][col] - arr[i][col];
        dp[i][col] = max(dp[i][col], 1);
    }
    for (int j = col - 1; j >= 0; j--) {
        dp[row][j] = dp[row][j + 1] - arr[row][j];
        dp[row][j] = max(dp[row][j], 1);
    }
    for (int i = row - 1; i >= 0; i--) {
        for (int j = col - 1; j>= 0; j--) {
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]);
            dp[i][j] = max(dp[i][j] - arr[i][j], 1);
        }
    }
    return dp[0][0];
}